package 归并算法;

/**
 * @Classname mergeTwoLists25
 * @Description TODO
 * @Date 2022/2/16 23:33
 * @Created by xjl
 */
public class mergeTwoLists25 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dumy = new ListNode(-1);

        ListNode curr = dumy;
        ListNode l = l1;
        ListNode r = l2;

        while (l != null && r != null) {
            if (l.val >= r.val) {
                curr.next = r;
                r = r.next;
            } else {
                curr.next = l;
                l = l.next;
            }
            curr = curr.next;
        }
        while (l != null) {
            curr.next = l;
            l = l.next;
            curr = curr.next;
        }
        while (r != null) {
            curr.next = r;
            r = r.next;
            curr = curr.next;
        }
        return dumy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
